package com.hardy.backtracking;

/**
 * 题目:
 现在你要研发一种新型的碎纸机，待粉碎的纸上面有一串数字，要求把纸粉碎成的几片上的数字的和尽量接近而不能超过给定的数字target number。比如：一片纸上的数字为12346，target number为50，那么就可以把纸粉碎为1、2、34、6，其加和为43，是所有粉碎方法中最接近50而不超过50的最优解。

 解释:
 题目换句话来理解就是有一串数字中间用+号来连接,使其结果小于或等于指定值的最优解.

 EG:

 题目 50 12346

 那么可以分为以下几种情况
 50 1+2+3+4+6=16

 50 12+3+4+6=25

 50 123+4+6=133

 50 1+23+4+6=34

 这道题就可以利用第一题二叉状态树想法来考虑,对于数字之间的空,可以选择插入+号和不插入加号
 * User: Ruijie Date: 2016/9/23
 */
public class PaperShredderProblem {

    public static int _paperShredder(String str,int target){
        int[] res=new int[1];
        _dfs(str,target,0,res);
        return res[0];
    }

    private static void _dfs(String str, int target,int curSum,int[] res) {
        if(str==null||"".equals(str)){
            res[0]=Math.max(curSum,res[0]);
        }else{
            for(int i=0;i<str.length();i++){
                int num=Integer.parseInt(str.substring(0,i+1));
                if(curSum+num>target){
                    return;
                }
                _dfs(str.substring(i+1),target,curSum+num,res);
            }
        }
    }

    public static void main(String[] args) {
        String s="12346";
        System.out.println(_paperShredder(s,50));
        DFS(num, 0);
    }

    static int sumTotal = 50;//规定最大值
    static String num = "12346";//规定字串
    static int max = 0;//得到最大值结果
    static boolean isCheck = true;//当前最大值结果是否唯一
    static StringBuilder builder = new StringBuilder();//当前最大值结果对应的方式

    private static void DFS(String num,int curSum){
        //递归结束条件
        if (num == null || "".equals(num)) {
            if (curSum == max) {
                isCheck = false;
                System.err.println(builder.toString()+"---max = "+max+"---check:"+isCheck);
                return ;
            }else if (curSum > max) {
                max = curSum;
                isCheck = true;
                //记录结果,打印
                System.err.println(builder.toString()+"---max = "+max+"---check:"+isCheck);
                builder.delete(0, builder.length());
                return ;
            }
        }
        //这里是循环的主体
        for (int i = 0; i < num.length(); i++) {
            int startNum = Integer.parseInt(num.substring(0,i+1));
            //剪枝,当总和大于total就没必要往后递归了
            if ((curSum + startNum)>sumTotal) {
                return;
            }
            //暂存结果,回溯的时候赋值给builder
            StringBuilder temp = new StringBuilder(builder);
            builder.append(startNum).append(" ");
            //下一步递归
            DFS(num.substring(i+1),curSum+startNum);
            builder = temp;
        }

    }
}
